package Day13.迷宫问题;

/**
 * @author HYHwtx
 * @version 1.0
 * @date 2022/2/19 9:28
 */
public class Demo1 {
    public static void main(String[] args) {
        int[][]map = new int[8][7];
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] =1;
        }
        for (int i = 1; i <= 6; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        map[2][2] = 1;
        // ↑上面是制作地图
        // 显示地图
        for (int[] r : map) {
            for (int col : r) {
                System.out.print(col + "\t");
            }
            System.out.println();
        }
        System.out.println("-------------------------");
        // 走迷宫
        findWay(map,1,1);//表示初始位置
        // 显示路线
        for (int[] row : map) {
            for (int col : row) {
                System.out.print(col + "\t");
            }
            System.out.println();
        }
    }


    /*
    * 思路：
    * 使用递归回溯的思想来解决老鼠出迷宫的问题
    1.findWay方法就是找出出迷宫的路径
    *2.如果找到，就返回true，否则就是false
    3.map就是二维数组，即表示的是迷宫
    4.i，j就是老鼠的位置，初始化的位置(0,0)
    5.因为我们是这个递规的找路，所以我们先要规定map数组的各个值得一个含义
    0表示可以走1表示障碍物2表示可以走 3表示走过，但是走不通是死路
    6.当map[6][5]=2就说明找到通路，就可以结束，否则就继续查找
    7.先确定老鼠找路策略下->右->上->左
*/
    public static boolean findWay(int[][]map,int i,int j){
        if (map[6][5]==2){
            return true;//路已经找到

        }else {
            if (map[i][j]==0){
                //该点不是已走过的
                map[i][j]=2;
                    if (findWay(map,i+1,j)){ //往下走
                        return true;
                    }else if (findWay(map,i,j+1)){ //往右走
                        return true;
                    }else if (findWay(map,i-1,j)){ //往上走
                        return true;
                    }else if (findWay(map,i,j-1)){ //往左走
                        return true;
                    }else { //都走不通
                        map[i][j] = 3;
                        return false;
                    }
                }else{
                        return false;
                    }
            }
        }
    }
